home *** CD-ROM | disk | FTP | other *** search
/ Hardcore Gamer Resource Kit / Hardcore Gamer Resource Kit - Disc 2.iso / Utils / UNIX / UNZIP520 / UNSHRINK.C < prev    next >
C/C++ Source or Header  |  1996-02-17  |  10KB  |  285 lines
  1. /*---------------------------------------------------------------------------
  2.  
  3.   unshrink.c                     version 1.21                     23 Nov 95
  4.  
  5.   Shrinking is basically a dynamic LZW algorithm with allowed code sizes of
  6.   up to 13 bits; in addition, there is provision for partial clearing of
  7.   leaf nodes.  PKWARE uses the special code 256 (decimal) to indicate a
  8.   change in code size or a partial clear of the code tree:  256,1 for the
  9.   former and 256,2 for the latter.  [Note that partial clearing can "orphan"
  10.   nodes:  the parent-to-be can be cleared before its new child is added,
  11.   but the child is added anyway (as an orphan, as though the parent still
  12.   exists).  When the tree fills up to the point where the parent node is
  13.   reused, the orphan is effectively "adopted."  Versions prior to 1.05 were
  14.   more affected due to their use of more pointers (to children and siblings
  15.   as well as parents).]
  16.  
  17.   This replacement version of unshrink.c was written from scratch.  It is
  18.   based only on the algorithms described in Mark Nelson's _The Data Compres-
  19.   sion Book_ and in Terry Welch's original paper in the June 1984 issue of
  20.   IEEE _Computer_; no existing source code, including any in Nelson's book,
  21.   was used.
  22.  
  23.   Memory requirements have been reduced in this version and are now no more
  24.   than the original Sam Smith code.  This is still larger than any of the
  25.   other algorithms:  at a minimum, 8K+8K+16K (stack+values+parents) assuming
  26.   16-bit short ints, and this does not even include the output buffer (the
  27.   other algorithms leave the uncompressed data in the work area, typically
  28.   called slide[]).  For machines with a 64KB data space this is a problem,
  29.   particularly when text conversion is required and line endings have more
  30.   than one character.  UnZip's solution is to use two roughly equal halves
  31.   of outbuf for the ASCII conversion in such a case; the "unshrink" argument
  32.   to flush() signals that this is the case.
  33.  
  34.   For large-memory machines, a second outbuf is allocated for translations,
  35.   but only if unshrinking and only if translations are required.
  36.  
  37.               | binary mode  |        text mode
  38.     ---------------------------------------------------
  39.     big mem   |  big outbuf  | big outbuf + big outbuf2  <- malloc'd here
  40.     small mem | small outbuf | half + half small outbuf
  41.  
  42.   Copyright 1994, 1995 Greg Roelofs.  See the accompanying file "COPYING"
  43.   in UnZip 5.20 (or later) source or binary distributions.
  44.  
  45.   ---------------------------------------------------------------------------*/
  46.  
  47.  
  48. #define UNZIP_INTERNAL
  49. #include "unzip.h"
  50.  
  51. static void  partial_clear  OF((__GPRO));
  52.  
  53. #ifdef DEBUG
  54. #  define OUTDBG(c) \
  55.    if ((c)<32 || (c)>=127) fprintf(stderr,"\\x%02x",(c)); else putc((c),stderr);
  56. #else
  57. #  define OUTDBG(c)
  58. #endif
  59.  
  60. /* HSIZE is defined as 2^13 (8192) in unzip.h */
  61. #define BOGUSCODE  256
  62. #define FLAG_BITS  parent        /* upper bits of parent[] used as flag bits */
  63. #define CODE_MASK  (HSIZE - 1)   /* 0x1fff (lower bits are parent's index) */
  64. #define FREE_CODE  HSIZE         /* 0x2000 (code is unused or was cleared) */
  65. #define HAS_CHILD  (HSIZE << 1)  /* 0x4000 (code has a child--do not clear) */
  66.  
  67. #define parent G.area.shrink.Parent
  68. #define Value  G.area.shrink.value /* "value" conflicts with Pyramid ioctl.h */
  69. #define stack  G.area.shrink.Stack
  70.  
  71.  
  72. /***********************/
  73. /* Function unshrink() */
  74. /***********************/
  75.  
  76. int unshrink(__G)
  77.      __GDEF
  78. {
  79. #if 0
  80.     static uch *stacktop = NULL;
  81. #else
  82.     uch *stacktop = stack + (HSIZE - 1);
  83. #endif
  84.     register uch *newstr;
  85.     int codesize=9, len, KwKwK, error;
  86.     shrint code, oldcode, freecode, curcode;
  87.     shrint lastfreecode;
  88.     unsigned int outbufsiz;
  89.  
  90.  
  91. /*---------------------------------------------------------------------------
  92.     Initialize various variables.
  93.   ---------------------------------------------------------------------------*/
  94.  
  95. #if 0
  96. /* SPC: no longer needed, stacktop is now an automatic variable that
  97.  *      is initialized on every unshrink() entry.
  98.  */
  99.     /* this is required for MACOS, but performance hit is minuscule */
  100.     if (stacktop == NULL)
  101.         stacktop = stack + (HSIZE - 1);
  102. #endif
  103.  
  104.     lastfreecode = BOGUSCODE;
  105.  
  106. #ifndef VMS     /* VMS uses its own buffer scheme for textmode flush(). */
  107. #ifndef SMALL_MEM
  108.     /* non-memory-limited machines:  allocate second (large) buffer for
  109.      * textmode conversion in flush(), but only if needed */
  110.     if (G.pInfo->textmode && !G.outbuf2 &&
  111.         (G.outbuf2 = (uch *)malloc(TRANSBUFSIZ)) == (uch *)NULL)
  112.         return PK_MEM3;
  113. #endif
  114. #endif /* !VMS */
  115.  
  116.     for (code = 0;  code < BOGUSCODE;  ++code) {
  117.         Value[code] = (uch)code;
  118.         parent[code] = BOGUSCODE;
  119.     }
  120.     for (code = BOGUSCODE+1;  code < HSIZE;  ++code)
  121.         parent[code] = FREE_CODE;
  122.  
  123.     G.realbuf = G.outbuf;   /* use normal outbuf unless we're a DLL routine */
  124. #ifdef DLL
  125.     if (G.redirect_data) {
  126.         G.realbuf = G.redirect_buffer;
  127.         outbufsiz = G.redirect_size;
  128.     } else
  129. #endif
  130.     if (G.pInfo->textmode)
  131.         outbufsiz = RAWBUFSIZ;
  132.     else
  133.         outbufsiz = OUTBUFSIZ;
  134.     G.outptr = G.realbuf;
  135.     G.outcnt = 0L;
  136.  
  137. /*---------------------------------------------------------------------------
  138.     Get and output first code, then loop over remaining ones.
  139.   ---------------------------------------------------------------------------*/
  140.  
  141.     READBITS(codesize, oldcode)
  142.     if (!G.zipeof) {
  143.         *G.outptr++ = (uch)oldcode;
  144.         OUTDBG((uch)oldcode)
  145.         ++G.outcnt;
  146.     }
  147.  
  148.     do {
  149.         READBITS(codesize, code)
  150.         if (G.zipeof)
  151.             break;
  152.         if (code == BOGUSCODE) {   /* possible to have consecutive escapes? */
  153.             READBITS(codesize, code)
  154.             if (code == 1) {
  155.                 ++codesize;
  156.                 Trace((stderr, " (codesize now %d bits)\n", codesize));
  157.             } else if (code == 2) {
  158.                 Trace((stderr, " (partial clear code)\n"));
  159.                 partial_clear(__G);   /* clear leafs (nodes with no children) */
  160.                 Trace((stderr, " (done with partial clear)\n"));
  161.                 lastfreecode = BOGUSCODE;  /* reset start of free-node search */
  162.             }
  163.             continue;
  164.         }
  165.  
  166.     /*-----------------------------------------------------------------------
  167.         Translate code:  traverse tree from leaf back to root.
  168.       -----------------------------------------------------------------------*/
  169.  
  170.         newstr = stacktop;
  171.         curcode = code;
  172.  
  173.         if (parent[curcode] == FREE_CODE) {
  174.             /* or (FLAG_BITS[curcode] & FREE_CODE)? */
  175.             KwKwK = TRUE;
  176.             Trace((stderr, " (found a KwKwK code %d; oldcode = %d)\n", code,
  177.               oldcode));
  178.             --newstr;   /* last character will be same as first character */
  179.             curcode = oldcode;
  180.         } else
  181.             KwKwK = FALSE;
  182.  
  183.         do {
  184.             *newstr-- = Value[curcode];
  185.             curcode = (shrint)(parent[curcode] & CODE_MASK);
  186.         } while (curcode != BOGUSCODE);
  187.  
  188.         len = (int)(stacktop - newstr++);
  189.         if (KwKwK)
  190.             *stacktop = *newstr;
  191.  
  192.     /*-----------------------------------------------------------------------
  193.         Write expanded string in reverse order to output buffer.
  194.       -----------------------------------------------------------------------*/
  195.  
  196.         Trace((stderr, "code %4d; oldcode %4d; char %3d (%c); string [", code,
  197.           oldcode, (int)(*newstr), (*newstr<32 || *newstr>=127)? ' ':*newstr));
  198.  
  199.         {
  200.             register uch *p;
  201.  
  202.             for (p = newstr;  p < newstr+len;  ++p) {
  203.                 *G.outptr++ = *p;
  204.                 OUTDBG(*p)
  205.                 if (++G.outcnt == outbufsiz) {
  206.                     Trace((stderr, "doing flush(), outcnt = %lu\n", G.outcnt));
  207.                     if ((error = flush(__G__ G.realbuf, G.outcnt, TRUE)) != 0)
  208.                         fprintf(stderr, "unshrink:  flush() error (%d)\n",
  209.                           error);
  210.                     Trace((stderr, "done with flush()\n"));
  211.                     G.outptr = G.realbuf;
  212.                     G.outcnt = 0L;
  213.                 }
  214.             }
  215.         }
  216.  
  217.     /*-----------------------------------------------------------------------
  218.         Add new leaf (first character of newstr) to tree as child of oldcode.
  219.       -----------------------------------------------------------------------*/
  220.  
  221.         /* search for freecode */
  222.         freecode = (shrint)(lastfreecode + 1);
  223.         /* add if-test before loop for speed? */
  224.         while (parent[freecode] != FREE_CODE)
  225.             ++freecode;
  226.         lastfreecode = freecode;
  227.         Trace((stderr, "]; newcode %d\n", freecode));
  228.  
  229.         Value[freecode] = *newstr;
  230.         parent[freecode] = oldcode;
  231.         oldcode = code;
  232.  
  233.     } while (!G.zipeof);
  234.  
  235. /*---------------------------------------------------------------------------
  236.     Flush any remaining data and return to sender...
  237.   ---------------------------------------------------------------------------*/
  238.  
  239.     if (G.outcnt > 0L) {
  240.         Trace((stderr, "doing final flush(), outcnt = %lu\n", G.outcnt));
  241.         if ((error = flush(__G__ G.realbuf, G.outcnt, TRUE)) != 0)
  242.             fprintf(stderr, "unshrink:  flush() error (%d)\n", error);
  243.         Trace((stderr, "done with flush()\n"));
  244.     }
  245.  
  246.     return PK_OK;
  247.  
  248. } /* end function unshrink() */
  249.  
  250.  
  251.  
  252.  
  253.  
  254. /****************************/
  255. /* Function partial_clear() */      /* no longer recursive... */
  256. /****************************/
  257.  
  258. static void partial_clear(__G)
  259.      __GDEF
  260. {
  261.     register shrint code;
  262.  
  263.     /* clear all nodes which have no children (i.e., leaf nodes only) */
  264.  
  265.     /* first loop:  mark each parent as such */
  266.     for (code = BOGUSCODE+1;  code < HSIZE;  ++code) {
  267.         register shrint cparent = (shrint)(parent[code] & CODE_MASK);
  268.  
  269.         if (cparent > BOGUSCODE && cparent != FREE_CODE)
  270.             FLAG_BITS[cparent] |= HAS_CHILD;   /* set parent's child-bit */
  271.     }
  272.  
  273.     /* second loop:  clear all nodes *not* marked as parents; reset flag bits */
  274.     for (code = BOGUSCODE+1;  code < HSIZE;  ++code) {
  275.         if (FLAG_BITS[code] & HAS_CHILD)    /* just clear child-bit */
  276.             FLAG_BITS[code] &= ~HAS_CHILD;
  277.         else {                              /* leaf:  lose it */
  278.             Trace((stderr, "%d\n", code));
  279.             parent[code] = FREE_CODE;
  280.         }
  281.     }
  282.  
  283.     return;
  284. }
  285.